#include <std.h>
#include <system.h>
#include <pio.h>
#include <error.h>
#include <type.h>

void *search_mem(unsigned char *start_pointer,unsigned char search_char,unsigned char *end_pointer);
int swapmem(char *m1,char *m2,size_t length);
int swap32mem(unsigned long *m1,unsigned long *m2,size_t length);
static unsigned long mem_table[1024];
static unsigned char flag_table[1024];
static u32 tag_table[1024]; 
int shift_table_down(int);
int shift_table_up(int);
extern unsigned long end;

#define set_allocated(n) flag_table[n]=1
#define set_free(n) flag_table[n]=NULL
#define is_allocated(n) (flag_table[n]&1)

#define make_entry(n,a) mem_table[n]=a
#define insert_entry(n,a) \
	shift_table_down(n); \
	mem_table[n]=a
#define delete_entry(n) shift_table_up(n)
#define allocation_size(n) (mem_table[n+1]-mem_table[n]) 

void *get_mem(size_t b);
int search_allocation(void *p);
int merge_free();
int free(void *p);
int reallocate(void *old,size_t b);
size_t avg_allocation_size();
int hash_location(void *p);
void init_mm();

void *search_mem(unsigned char *start_pointer,unsigned char search_char,unsigned char *end_pointer)
{
	unsigned char *search;
	assert(start_pointer<end_pointer,2);
	for(search=start_pointer;search<end_pointer;search++)	{
		if(*search==search_char)
			return search;
	}
	return NULL;
}

int swapmem(char *m1,char *m2,size_t length)
{
	char *temp;
	while(--length>0)	{
		*temp=*m1;
		*m1=*m2;
		*m2=*temp;
	}
}

int swap32mem(unsigned long *m1,unsigned long *m2,size_t length)
{
	unsigned long *temp;
	while(--length>0)	{
		*temp=*m1;
		*m1=*m2;
		*m2=*temp;
	}
}
	

int shift_table_down(int start)
{
	int i;
	for(i=1023;i>start;i--)	{
		mem_table[i]=mem_table[i-1];
		flag_table[i]=flag_table[i-1];
	}
	mem_table[start]=NULL;
	return NULL;
}

int shift_table_up(int start)
{
	int i;
	for(i=start;i<1023;i++)	{
		mem_table[i]=mem_table[i+1];
		flag_table[i]=flag_table[i+1];
	}
	return NULL;
}

void *get_mem(size_t b)
{
	int i;
	spin_lock mal;
	acquire_spin_lock(&mal);
	for(i=0;i<1024;i++)	{
		if(is_allocated(i)==NULL)	{
			if(allocation_size(i)>b)	{
				shift_table_down(i+1);
				make_entry(i+1,mem_table[i]+b);
				set_allocated(i);
				release_spin_lock(&mal);
				//printf("[memr:%x:%d]",mem_table[i],b);
				return (void *)mem_table[i];
			}
			else if(allocation_size(i)==b)	{
				set_allocated(i);
				release_spin_lock(&mal);
				//printf("[memr:%x:%d]",mem_table[i],b);
				return (void *)mem_table[i];
			}
		}
	}
	release_spin_lock(&mal);
	return NULL;
}

void *get_mem_tag(size_t b,u32 tag)
{
	int i;
	spin_lock mal;
	acquire_spin_lock(&mal);
	for(i=0;i<1024;i++)	{
		if(is_allocated(i)==NULL)	{
			if(allocation_size(i)>b)	{
				shift_table_down(i+1);
				make_entry(i+1,mem_table[i]+b);
				set_allocated(i);
				tag_table[i]=tag;
				//printf("[memr:%x:%d]",mem_table[i],b);
				release_spin_lock(&mal);
				return (void *)mem_table[i];
			}
			else if(allocation_size(i)==b)	{
				set_allocated(i);
				tag_table[i]=tag;
				//printf("[memr:%x:%d]",mem_table[i],b);
				release_spin_lock(&mal);
				return (void *)mem_table[i];
			}
		}
	}
	release_spin_lock(&mal);
	return NULL;
}


void *get_tag(u32 tag)
{
	int i;
	spin_lock c;
	acquire_spin_lock(&c);
	for(i=0;i<1024;i++)	{
		if(tag_table[i]==tag)	{
			if(is_allocated(i))
				return (void *)mem_table[i];
		}
	}
	return NULL;
}

int search_allocation(void *p)
{
	int i;
	for(i=0;i<1024;i++)	{
		if((mem_table[i])==(unsigned long)p)
			return i;
	}
	printf("ERROR:MEMORY FREE FAILED");
	while(1);
}

int merge_free()
{
	int i,merges=0;
	for(i=0;i<1023;i++)
	{
		if(is_allocated(i)==NULL && is_allocated(i+1)==NULL && ((mem_table[i+1])!=0xffffffff))	{
			shift_table_up(i+1);
			merges++;
		}
	}
	return merges;
}

int free(void *p)
{
	int i;
	spin_lock mfr;
	acquire_spin_lock(&mfr);
	i=search_allocation(p);
	set_free(i);
	tag_table[i]=0xffffffff;
	i=1;
	while(i)	{
		i=merge_free();
	}
	//printf("[free:%x]",mem_table[i]);
	release_spin_lock(&mfr);
	return NULL;
}

int reallocate(void *old,size_t b)
{
	int i;
	size_t size;
	void *temp;
	spin_lock mre;
	acquire_spin_lock(&mre);
	temp=old;
	i=search_allocation(old);
	size=allocation_size(i);
	free(old);
	old=get_mem(b);
	memcpy(old,temp,size);
	//printf("[memr:%x:%d]",mem_table[i],b);
	release_spin_lock(&mre);
	return NULL;
}

size_t avg_allocation_size()
{
	int i=0;
	size_t avg;
	while(allocation_size(i)!=NULL)	{
		avg+=allocation_size(i);
		i++;
	}
	avg/=1024;
	return avg;
}

int hash_location(void *p)
{
	int temp;
	temp=(int)(p-mem_table[0]);
	temp/=avg_allocation_size();
	return temp;
}

int show_table()
{
	int i;
	printf("\nDISPLAYING MEMORY TABLE:");
	for(i=0;i<30;i++)	{
		if(is_allocated(i))	{
			printf("\n%d\t0x%x\tALLOCATED",i,mem_table[i]); 
		}
		else	{
			printf("\n%d\t0x%x\tFREE",i,mem_table[i]);
		}
	}
}


void init_mm()
{
	int i;
	printf("\nInitiating memory tables");
	for(i=0;i<1024;i++)	{
		mem_table[i]=0xffffffff;
		flag_table[i]=NULL;
		tag_table[i]=0xffffffff;
	}
	make_entry(0,end);	
}

